// 寻找两个等长有序序列的中位数的算法
#include<iostream>
#include<vector>
using namespace std;

// 求a[s..t]序列的前半子序列
void prepart(int &s,int &t)
{
	int m=(s+t)/2;
	t=m;
}

// 求a[s..t]序列的后半子序列
void postpart(int &s, int &t)	
{
	int m=(s+t)/2;
	
	// 序列中有奇数个元素
	if ((s+t)%2 == 0)
		s = m;
	
	// 序列中有偶数个元素
	else
		s = m+1;
}

// 打印数组
void display(int a[],int s,int t)
{
	for (int i=s; i<=t; i++)
		printf("%d ",a[i]);
	printf("\t");
}

// 递归法
// 求两个有序序列a[s1..t1]和b[s2..t2]的中位数
int midnum11(int a[],int s1,int t1,int b[],int s2,int t2)
{
	int m1,m2;
	
	// 两序列只有一个元素时返回较小者
	if (s1==t1 && s2==t2)
		return a[s1] < b[s2] ? a[s1] : b[s2];
	else
	{
		// 求a的中位数
		m1=(s1+t1)/2;
		
		// 求b的中位数
		m2=(s2+t2)/2;
		
		// 两中位数相等时返回该中位数
		if (a[m1] == b[m2])
		{
			printf("%d=%d:  ", a[m1], b[m2]);
			return a[m1];
		}
		
		// 当a[m1]<b[m2]时
		if (a[m1]<b[m2])
		{
			// a取后半部分
			postpart(s1,t1);
			
			// b取前半部分
			prepart(s2,t2);

			printf("%d<%d:  ", a[m1], b[m2]);
			
			// 打印
			printf("a:"); display(a, s1, t1);
			printf("b:"); display(b, s2, t2);
			printf("\n");
			
			// 求中位数
			return midnum11(a,s1,t1,b,s2,t2);
		}
		
		// 当a[m1]>b[m2]时
		else
		{
			// a取前半部分
			prepart(s1, t1);
			
			// b取后半部分
			postpart(s2, t2);
			
			// 打印
			printf("%d>%d:  ", a[m1], b[m2]);
			printf("a:"); display(a, s1, t1);
			printf("b:"); display(b, s2, t2);
			printf("\n");
			
			// 求中位数
			return midnum11(a, s1, t1, b, s2, t2);
		}
	}
}

// 求两个有序序列a和b的中位数
int midnum1(int a[],int b[],int n) 	
{
	return midnum11(a, 0, n-1, b, 0, n-1);
}

// 迭代法
// 求两个有序序列a和b的中位数
int midnum2(int a[], int b[], int n)
{
	// 标记查找范围
	int s1,t1,m1,s2,t2,m2;
	s1=0; t1=n-1;
	s2=0; t2=n-1;
	while (s1!=t1 || s2!=t2)
	{
		m1=(s1+t1)/2;
		m2=(s2+t2)/2;
		
		// 查找到中位数
		if (a[m1]==b[m2])
			return a[m1];
		
		// 更新查找范围
		if (a[m1]<b[m2])
		{
			postpart(s1,t1);
			prepart(s2,t2);
		}
		else
		{
			prepart(s1,t1);
			postpart(s2,t2);
		}
	}
	return a[s1]<b[s2]?a[s1]:b[s2];
}

int main()
{
	// 初始化两个有序序列
	int a[] = {1, 3, 4, 6, 9};
	int b[] = {2, 3, 5, 8, 10};
	
	// 数组的长度
	int n = sizeof(a) / sizeof(a[0]);
	
	// 打印两数组
	printf("a:"); display(a, 0, n-1);
	printf("b:"); display(b, 0, n-1); printf("\n");
	
	// 寻找中位数
	printf("中位数:%d\n", midnum1(a,b,n));
	return 0;
}
